#include "RBTree.h"
RBTree::RBTree(){}
// 含参构造（传入排序规则）
RBTree::RBTree(Rule i)
{
    // 生成空节点，代表根节点的父节点和叶子节点
    Nil = BuyNode();
    root = Nil;				// 此时root就是空节点
    Nil->color = BLACK;		// 红黑树规定叶子节点为黑色
    total = 0;				// 此时红黑树中没有实际节点
    this->rule = i;			// 设置当前红黑树排序规则
}
//析构函数
RBTree::~RBTree()
{
    destroy(); //销毁创建的非Nil结点
    delete Nil;    //最后删除Nil结点
    Nil = NULL;
}
// 重新填充并获取vector
vector<StudentInfo*> RBTree::getVec()
{
    this->vStu.clear();
    this->vStu.reserve(total);
    inorder(root);
    return this->vStu;
}
// 按从小到大存储学生信息
void RBTree::inorder(RBTNode* root)
{
    if (root != Nil)
    {
        inorder(root->left);
        this->vStu.push_back(root->key);
        inorder(root->right);
    }
}
bool RBTree::moreThan(StudentInfo* si1, StudentInfo* si2)
{
    switch (rule)
    {
    case STUID: // 按学号排序
        return si1->getStuId() > si2->getStuId();
    case SCORE: // 按绩点排序
        return si1->getScore() > si2->getScore();
    case CREDIT: // 按总学分排序
        return si1->getCredit() > si2->getCredit();
    case USERNAME: // 按用户名查找
        return si1->getUsername() > si2->getUsername();
    }
    return false;
}
bool RBTree::equalTo(StudentInfo* si1, StudentInfo* si2)
{
    switch (rule)
    {
    case STUID: // 按学号排序
        return si1->getStuId() == si2->getStuId();
    case SCORE: // 按总学分排序
        return si1->getScore() == si2->getScore() && si1->getStuId() == si2->getStuId();
    case CREDIT: // 按绩点排序
        return si1->getCredit() == si2->getCredit() && si1->getStuId() == si2->getStuId();
    case USERNAME: // 按用户名查找
        return si1->getUsername() == si2->getUsername();
    }
    return false;
}

// 插入节点（寻找适当位置插入）
bool RBTree::Insert(StudentInfo* newValue)
{
    RBTNode* pre = Nil;    // pre维护当前节点的父节点指针
    RBTNode* cur = root;    // cur维护当前节点指针
    while (cur != Nil)
    {
        pre = cur;    // 维护s的父节点
        // 当前节点大于新节点
        if (moreThan(cur->key, newValue))
        {
            cur = cur->left;
        }
        else
        {
            cur = cur->right;
        }
    }
    //循环后cur==Nil
    cur = BuyNode(newValue);    // 申请结点
    // 该情况为对空树创建第一个节点
    if (pre == Nil)    // 如果父节点pre是根节点，第一次root指向Nil，所以pre==Nil
    {
        root = cur; // 设置该节点为根节点
        root->parent = Nil; // 设置该节点的父节点为空节点
    }
    else
    {
        // 父节点不是根节点
        if (moreThan(pre->key, newValue))
        {
            pre->left = cur;
        }
        else
        {
            pre->right = cur;
        }

        cur->parent = pre;    // 设置新结点cur的父节点为pre
    }

    //调整平衡
    Insert_Fixup(cur);
    return true;
}

//删除key结点(先查找，再调用内部删除)
bool RBTree::RemoveNode(StudentInfo* key)
{
    RBTNode* t;
    if ((t = Search(root, key)) != Nil)
    {
        Remove(t);
        delete t;
        --total;
        return true;
    }
    else
    {
        cout << "Key is not exist." << endl;
        return false;
    }
}

//申请结点，将结点的颜色初始化为红色，初始化结点的关键字，其他的初始化为空
RBTree::RBTNode* RBTree::BuyNode(StudentInfo* newValue)
{
    RBTNode* s = new RBTNode();
    assert(s != NULL);
    s->color = RED;
    s->left = s->right = s->parent = Nil;
    s->key = newValue;
    ++total;
    return s;
}

//左转，对z结点左转
void RBTree::LeftRotate(RBTNode* z)
{
    RBTNode* y = z->right;    //用y指向要转动的z结点
    z->right = y->left;
    if (y->left != Nil)    //y所指结点的左结点不为空
    {
        y->left->parent = z;
    }
    y->parent = z->parent;
    if (root == z)    //z就是根节点
    {
        root = y;
    }
    else if (z == z->parent->left)    //z在左结点
    {
        z->parent->left = y;
    }
    else    //z在右结点
    {
        z->parent->right = y;
    }
    y->left = z;
    z->parent = y;
}

//右转，对z结点进行右转
void RBTree::RightRotate(RBTNode* z)
{
    RBTNode* y = z->left;
    z->left = y->right;
    if (y->right != Nil)
    {
        y->right->parent = z;
    }
    y->parent = z->parent;
    if (root == z)    //如果z是根结点
    {
        root = y;
    }
    else if (z == z->parent->left)    //z在左结点
    {
        z->parent->left = y;
    }
    else    //z在右结点
    {
        z->parent->right = y;
    }
    y->right = z;
    z->parent = y;
}

//插入后的调整函数
void RBTree::Insert_Fixup(RBTNode* cur)
{
    RBTNode* uncle;    // 叔结点（父结点的兄弟结点）
    while (cur->parent->color == RED)    // 父节点的颜色也为红色
    {
        if (cur->parent == cur->parent->parent->left)    // 父节点是左结点
        {
            uncle = cur->parent->parent->right;

            if (uncle->color == RED)    //叔结点为红色
            {
                //父节点和叔结点都变为黑色
                cur->parent->color = BLACK;
                uncle->color = BLACK;
                //祖父结点变为红色
                cur->parent->parent->color = RED;
                //将s指针指向祖父结点，下一次循环继续判断祖父的父节点是否为红色
                cur = cur->parent->parent;
            }
            else    //没有叔结点，或叔结点为黑色(经过多次循环转换，叔结点可能为黑)
            {
                if (cur == cur->parent->right)    //如果调整的结点在右结点
                {
                    cur = cur->parent;    //先将s指向s的父结点
                    LeftRotate(cur);    //再左转
                }
                //如果调整的结点在左结点,将s的父节点变为黑色，将祖父的结点变为红色，将s的祖父结点右转
                cur->parent->color = BLACK;
                cur->parent->parent->color = RED;
                RightRotate(cur->parent->parent);
            }
        }
        else
        {
            if (cur->parent == cur->parent->parent->right)    //父节点是右结点
            {
                uncle = cur->parent->parent->left;
                if (uncle->color == RED)    //叔结点为红色
                {
                    //父节点和叔结点都变为黑色
                    cur->parent->color = BLACK;
                    uncle->color = BLACK;
                    //祖父结点变为红色
                    cur->parent->parent->color = RED;
                    //将s指针指向祖父结点，下一次循环继续判断祖父的父节点是否为红色
                    cur = cur->parent->parent;
                }
                else    //没有叔结点，或叔结点为黑色(经过多次循环转换，叔结点可能为黑)
                {
                    if (cur == cur->parent->left)    //如果调整的结点在左结点
                    {
                        cur = cur->parent;    //先将s指向s的父结点
                        RightRotate(cur);    //再右转
                    }
                    //如果调整的结点在右结点,将s的父节点变为黑色，将祖父的结点变为红色，将s的祖父结点右转
                    cur->parent->color = BLACK;
                    cur->parent->parent->color = RED;
                    LeftRotate(cur->parent->parent);
                }
            }
        }
    }
    root->color = BLACK;    //最后始终将根节点置为黑色
}

// 返回学生信息的位置
StudentInfo* RBTree::search(StudentInfo* dst)
{
    RBTNode* temp = Search(this->root, dst);
    cout << "search over" << endl;
    if (temp != Nil)
    {
        cout << "search successed" << endl;
        return temp->key;
    }
    else
    {
        cout << "search failed" << endl;
    }
    return nullptr;
}

//查找key结点
RBTree::RBTNode* RBTree::Search(RBTNode* root, StudentInfo* dst)
{
    if (root == Nil)    //root为空，或key和根的key相同
    {

        return Nil;
    }

    if (equalTo(root->key, dst))
    {
        cout << root->key->getStuId() << " = " << dst->getStuId() << endl;
        return root;
    }
    if (moreThan(root->key, dst))
    {
        cout << root->key->getStuId() << " > " << dst->getStuId() << endl;
        return Search(root->left, dst);
    }
    else
    {
        cout << root->key->getStuId() << " < " << dst->getStuId() << endl;
        return Search(root->right, dst);
    }
}

//将u的子节点指针指向u改变指向v，将v的父节点改变为指向u的父节点
void RBTree::Transplant(RBTNode* u, RBTNode* v)
{
    if (u->parent == Nil)    //u的父节点为空
    {
        root = v;    //直接令根root为v
    }
    else if (u == u->parent->left)    //u父节点不为空，且u在左子树
    {
        u->parent->left = v;
    }
    else    //u在左子树
    {
        u->parent->right = v;
    }
    v->parent = u->parent;
}

//找到最左结点(最小)
RBTree::RBTNode* RBTree::Minimum(RBTNode* x)
{
    if (x->left == Nil)
    {
        return x;
    }
    return Minimum(x->left);
}

//删除红黑树结点z
void RBTree::Remove(RBTNode* z)
{
    RBTNode* x = Nil;
    RBTNode* y = z;    //y记住传进来的z结点
    Color ycolor = y->color;  //
    if (z->left == Nil) //z只有右孩子
    {
        x = z->right;
        Transplant(z, z->right);
    }
    else if (z->right == Nil) //z只有右孩子
    {
        x = z->left;
        Transplant(z, z->left);
    }
    else //右左孩子和右孩子
    {
        y = Minimum(z->right);    //y是z右子树的的最左子树
        ycolor = y->color;
        x = y->right;
        if (y->parent == z)    //z的右子结点没有左节点或为Nil
        {
            x->parent = y;
        }
        else    //z的右子结点有左节点或为Nil
        {
            Transplant(y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        Transplant(z, y);
        //改变指向
        y->left = z->left;
        z->left->parent = y;
        y->color = z->color;
    }
    if (ycolor == BLACK)
    {
        Remove_Fixup(x);
    }
}

//红黑树删除调整
void RBTree::Remove_Fixup(RBTNode* x)
{
    while (x != root && x->color == BLACK) //当结点x不为根并且它的颜色不是黑色
    {
        if (x == x->parent->left)        //x在左子树
        {
            RBTNode* w = x->parent->right;    //w是x的兄结点

            if (w->color == RED)    //情况1
            {
                w->color = BLACK;
                x->parent->color = RED;
                LeftRotate(x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK)    //情况2
            {
                w->color = RED;
                x = x->parent;
            }
            else
            {
                if (w->right->color == BLACK)        //情况3
                {
                    w->color = RED;
                    w->left->color = BLACK;
                    RightRotate(w);
                    w = x->parent->right;
                }
                //情况4
                w->color = w->parent->color;
                w->parent->color = BLACK;
                w->right->color = BLACK;
                LeftRotate(x->parent);
                x = root;    //结束循环

            }
        }
        else        //x在右子树
        {
            RBTNode* w = x->parent->left;
            if (w->color == RED)    //情况1
            {
                w->parent->color = RED;
                w->color = BLACK;
                RightRotate(x->parent);
                w = x->parent->left;
            }
            if (w->left->color == BLACK && w->right->color == BLACK)        //情况2
            {
                w->color = RED;
                x = x->parent;
            }
            else
            {
                if (w->left->color == BLACK)    //情况3
                {
                    w->right->color = BLACK;
                    w->color = RED;
                    LeftRotate(w);
                    w = x->parent->left;
                }
                //情况4
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                RightRotate(x->parent);
                x = root;    //结束循环
            }
        }
    }
    x->color = BLACK;
}

// 销毁红黑树
void RBTree::destroy()
{
    this->Destroy(this->root);
}

// 递归销毁红黑树
void RBTree::Destroy(RBTNode*& root)
{
    if (root == Nil)
    {
        return;
    }
    if (root->left != Nil)
    {
        Destroy(root->left);
    }
    if (root->right != Nil)
    {
        Destroy(root->right);
    }
    delete root;
    root = nullptr;
}

//中序遍历打印结点详细的结点颜色
void RBTree::InOrderPrint()
{
    InOrderPrint(root);
}

//中序遍历打印结点详细的结点颜色
void RBTree::InOrderPrint(RBTNode* node)
{
    if (node == Nil)
    {
        return;
    }
    if (node->left != NULL)
    {
        InOrderPrint(node->left);
    }
    cout << node->key << "(" << ((node->color == BLACK) ? "BLACK" : "RED") << ")" << " ";
    if (node->right != Nil)
    {
        InOrderPrint(node->right);
    }
}
